#include<stdio.h>
#include<stdlib.h>

int min_heapify(int *a,int i,int size)
{

	int l=2*i-1;
	int r=2*i;
	i=i-1;
	int asize=size;
	int largest,temp;
//	printf("size of a %d\n",asize);
	if(l>asize) return 0;
	if((l<asize)&&(a[l]<a[i]))
	{
		largest=l;
	}
	else
	{
		largest=i;
	}
	if((r<asize)&&(a[r]<a[largest]))
	{
		largest=r;
	}
	if(largest!=i)
	{
		temp=a[i];
		a[i]=a[largest];
		a[largest]=temp;
		min_heapify(a,largest+1,size);
	}
}

int build_heap(int *a,int size)
{
	int i;
	for(i=size/2;i>0;i--) min_heapify(a,i,size);
	return 0;
}

int heap_sort(int *a,int size)
{
	int temp,i;
	build_heap(a,size);
	for(i=0;i<size;i++) printf("%d, ",a[i]);
	for(i=size;i>1;i--)
	{
		temp=a[0];
		a[0]=a[size-1];
		a[size-1]=temp;
		size=size-1;
		min_heapify(a,1,size);
	}
}
int main()
{
	int i,j,k;
	int temp=0;
	int sum=0;
	int size=5;
	int b[5]={1,2,3,4,10};
	build_heap(b,size);
	while(size>1)
	{
	for(i=0;i<2;i++)
	{
		temp+=b[0];
		if(i==0)
		{
			printf("%d ",b[0]);
			b[0]=b[size-1];
			size=size-1;
			min_heapify(b,1,size);
		}
		else
		{
			sum+=temp;
			printf("%d ",b[0]);
			b[0]=temp;
			temp=0;
			min_heapify(b,1,size);
		}
	}
	printf("\n");
	}

	printf("sum is %d\n",b[0]);
}
